The advantages of using a network comprising switching elements which route packets of data through the network on the basis of an address contained within the packet are known. Such networks are commonly called binary routing networks. A specific example is the butterfly or banyan network. In this type of network, there exists only one unique path between any two network terminations. The network comprises a plurality of stages each having a number of switch nodes. The stages are interconnected by means of links. Each switch node, upon receipt of a packet, is responsive to contents of an address field to properly route the packet to the next stage via an interconnecting link. One such system of this type was disclosed in the U.S. Pat. No. 4,491,945 of Jonathan S. Turner. The system disclosed in the Turner patent is illustrated in FIGS. 1 and 2 which show an illustrative packet switching system having a plurality of local offices 102, 103, 108, and 109, and a plurality of toll offices 104 through 107 serving a plurality of customers such as customers 100 or 110. As described in the Turner application, call setup and call reply packets are utilized by the customers in order to set up a logical path through the different packet switching networks. The system works using two different types of packets for the communication of data. Trunk packets are utilized for the transmission of information on high-speed digital trunks such as trunk 118 between trunk controllers 131 and 140. The transfer of information between trunk controllers through a packet switching network is via switch packets such as communication between trunk controllers 130 and 131 via packet switching network 116. A switch packet comprises the trunk packet plus additional information necessary for routing the packet through the packet switching network. A trunk controller is responsive to a trunk packet to form the switch packet and, in particular, to insert into the destination trunk controller field of the switch packet the address necessary to route the packet through the packet switching network. The necessary logical-to-physical address translation is stored in the trunk controller by an associated central processor such as central processor 115 in response to the call setup and call reply packets.
A prior art switch packet is illustrated in FIG. 4. As the switch packet of FIG. 4 is routed through switching network 116, each stage in the network rotates the contents of the destination trunk controller field to the left by 2 bits. This positions the destination trunk controller address so that the next stage can respond to the two most significant bits. For example, FIG. 5 illustrates the switch packet of FIG. 4 after it has been transferred through the first stage.
Whereas the scheme of rotating the address field allows the next sequential stage to immediately respond to the address, it suffers from the problem of not allowing the use of broadcast packets (those which are sent to all nodes) and requires complex circuitry for performing the address rotation.